The enormous success of devices such as smartphones and tablets has propelled the field of context aware computing into the forefront of research and development. Every application in today's smartphone market utilizes location information to not only provide relevant information to the user but also place relevant advertisements to generate revenue. A very important piece of the puzzle in this framework is indoor localization. The most popular way of doing indoor localization is to measure received signal strength (RSS) values from the neighboring WIFI access points and process them using a localization algorithm to find a location estimate.
RSS based localization algorithms come in many different flavors, they either utilize the empirical relationship between the observed path-loss and distance or the spatial locality of observed RSS vector for estimating the location. Some of the most popular techniques are Maximum Likelihood Estimate (MLE), Least Square Estimate (LSE), Fingerprinting and Sequence Based Localization (SBL). Some of the most popular techniques are Maximum Likelihood Estimate (MLE) [1], Least Square Estimate (LSE) [2], Fingerprinting [3] [4] and Sequence Based Localization (SBL) [5] [6]. A consequence of the complex nature and the many tradeoffs involved in setting up an indoor localization system is that each technique may have better utility in some dimension than the others. The localization accuracy for every algorithm could be potentially affected by various factors such as RF propagation loss, multi-path fading, and the location and density of reference nodes.
SBL utilizes periodic beacon transmission from the fixed beacon nodes. Target nodes receive these beacon packets and generate a RSS vector. A ranked version of this RSS vector called a sequence is then compared against a set of ideal sequences generated based on the known location of the beacon nodes. The co-ordinates corresponding to the best matched ideal sequence are then given out as the localization result. This is possible because each sequence corresponds to a unique region in the 2-dimensional localization space, these regions are referred to as SBL faces. SBL exploits this unique geometric relationship for performing localization. SBL assumes all beacon nodes transmit at equal power, therefore the size, shape and the total number of faces only depends upon the number of beacon nodes and their positions. To understand how ideal sequences are generated, consider two beacon nodes A, B as depicted in FIG. 1(A), with equal transmit power PTA=PTB. In an ideal case, the perpendicular line bisector of AB represents the line where received signal strength value from beacon node A and B is equal PRA=PRB. This equal RSS line divides the localization space into two faces as shown in FIG. 1(A). At any point in the face that includes node A theoretically RSS value (PRA) from node A should be greater than the RSS value (PRB) from node B. Therefore, the sequence (ranked RSS vector) for this face is given by (1, 2), similarly for the second region it is (2, 1). Therefore, if the receiver has the beacon node topology information it can approximately localize itself at the centroid of one of the two faces. When the same principle is extended to greater numbers of beacons, the number of regions grow polynomially improving the accuracy of the technique. FIG. 1(B) shows faces and corresponding sequences for a 4-node topology.
It has been shown in [5] that the number of geometrically valid sequences is O(n4), out of O(n!) total possible sequences. This gives this algorithm noise immunity as well as polynomial time complexity. In a real setting due to noise and multipath fading, the comparison of the observed sequence and the ideal sequences doesn't yield an exact match. To overcome this problem, the SBL algorithm uses the Kendal Tau correlation coefficient as a comparison metric between the sequences.